home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 118_01 / pattern.bds < prev    next >
Encoding:
Text File  |  1980-07-08  |  10.5 KB  |  551 lines
  1. /* Pattern and set routines for Software Tools
  2.  * source:  pattern.bds
  3.  * version: November 26, 1981
  4.  */
  5.  
  6. /*
  7. note:  only addstr() and addset are translated and debugged
  8. */
  9.  
  10. #include tools.h
  11.  
  12.  
  13.  
  14. /*  addstr - add s to str[j] if it fits, increment j */
  15.  
  16. addstr (s, str, j, maxsiz)
  17. char *s, *str;
  18. int  *j,  maxsiz;
  19. {
  20.     int i;
  21.  
  22.     for (i = 0; s[i] != EOS; i++) {
  23.         if (addset (s[i], str, j, maxsiz) == NO) {
  24.             return(NO);
  25.         }
  26.     }
  27.     return(YES);
  28. }
  29.  
  30.  
  31. /* comment out ----------
  32.  
  33. /*  catsub - add replacement text to end of  new */
  34.  
  35. catsub (lin, from, to, sub, new, k, maxnew)
  36. char *lin;
  37. int from [10], to [10];
  38. char *sub, *new;
  39. int k, maxnew;
  40. {
  41.     int i, j, ri;
  42.  
  43.     for (i = 0; sub[i] != EOS; i++) {
  44.         if (sub[i] == DITTO) {
  45.             i++;
  46.             ri = sub[i] + 1;
  47.             for (j = from [ri]; j < to [ri]; j++) {
  48.                 addset (lin[j], new, k, maxnew);
  49.             }
  50.         }
  51.         else {
  52.             addset (sub[i], new, k, maxnew);
  53.         }
  54.     }
  55. }
  56.  
  57. /*  getpat - convert str into pattern */
  58.  
  59. getpat (str, pat)
  60. char *str, *pat;
  61. {
  62.     return (makpat (str, 1, EOS, pat));
  63. }
  64.  
  65. /*  maksub - make substitution string in sub */
  66.  
  67. maksub (arg, from, delim, sub)
  68. char *arg;
  69. int from;
  70. char delim;
  71. char *sub;
  72. {
  73.     int i, j;
  74.  
  75.     j = 1;
  76.     for (i = from; arg[i] != delim && arg[i] != EOS; i++) {
  77.         if (arg[i] == AND) {
  78.             addset (DITTO, sub, j, MAXPAT);
  79.             addset (0, sub, j, MAXPAT);
  80.         }
  81.         else if ( arg[i] == ESCAPE &&
  82.                   type(arg[i + 1]) == DIGIT
  83.                 ) {
  84.             i++
  85.             addset (DITTO, sub, j, MAXPAT);
  86.             addset (arg[i] - DIG0, sub, j, MAXPAT);
  87.         }
  88.         else {
  89.             addset (esc (arg, i), sub, j, MAXPAT);
  90.         }
  91.     }
  92.  
  93.     if (arg[i] != delim) {
  94.         /* missing delimiter */
  95.         return(ERR);
  96.     }
  97.     else if (addset (EOS, sub, j, MAXPAT) == NO) {
  98.         /* no room */
  99.         return(ERR);
  100.     }
  101.     else {
  102.         return(i);
  103.     }
  104. }
  105.  
  106. /*  makpat --- make pattern from arg (from)
  107.  *             terminate at delim
  108.  */
  109.  
  110. int makpat (arg, from, delim, pat)
  111. char *arg;
  112. int from;
  113. char delim;
  114. char *pat;
  115. {
  116.     int i, j, lastcl, lastj, lj;
  117.     int tagnst, tagnum, tagstk[9];
  118.  
  119.     /* pat index */
  120.     j = 1;
  121.     lastj = 1;
  122.     lastcl = 0;
  123.     tagnum = 0;
  124.     tagnst = 0;
  125.     for (i = from; arg[i] != delim && arg[i] != EOS; i++) {
  126.         lj = j;
  127.         if (arg[i] == ANY) {
  128.             addset (ANY, pat, j, MAXPAT);
  129.         }
  130.         else if (arg[i] == BOL & i == from) {
  131.             addset (BOL, pat, j, MAXPAT);
  132.         }
  133.         else if (arg[i] == EOL & arg (i + 1) == delim){
  134.             addset (EOL, pat, j, MAXPAT);
  135.         }
  136.         else if (arg[i] == CCL) {
  137.             if (getccl (arg, i, pat, j) == ERR) {
  138.                 return (ERR);
  139.             }
  140.         }
  141.         else if (arg[i] == CLOSURE & i > from) {
  142.             lj = lastj;
  143.             if ( pat (lj) == BOL || 
  144.                  pat (lj) == EOL || 
  145.                  pat (lj) == CLOSURE ||
  146.                  pat (lj) == START_TAG || 
  147.                  pat (lj) == STOP_TAG
  148.                ) {
  149.                 break;
  150.             }
  151.             lastcl = stclos(pat, j, lastj, lastcl);
  152.         }
  153.         else if (arg[i] == START_TAG) {
  154.             if (tagnum >= 9) {
  155.             /* too many tagged sub-patterns */
  156.                 break;
  157.             }
  158.             tagnum++;
  159.             tagnst++;
  160.             tagstk [tagnst] = tagnum;
  161.             addset (START_TAG, pat, j, MAXPAT);
  162.             addset (tagnum, pat, j, MAXPAT);
  163.         }
  164.         else if (arg[i] == STOP_TAG & tagnst > 0) {
  165.             addset (STOP_TAG, pat, j, MAXPAT);
  166.             addset(tagstk[tagnst], pat, j, MAXPAT);
  167.             tagnst--;
  168.         }
  169.         else {
  170.             addset (CHAR, pat, j, MAXPAT);
  171.             addset (esc (arg, i), pat, j, MAXPAT);
  172.         }
  173.         lastj = lj;
  174.     }
  175.     if (arg[i] != delim) {
  176.         /*  terminated early */
  177.         return(ERR);
  178.     }
  179.     else if (addset (EOS, pat, j, MAXPAT) == NO) {
  180.         /*  no room */
  181.         return(ERR);
  182.     }
  183.     else if (tagnst != 0) {
  184.         return(ERR);
  185.     }
  186.     else {
  187.         return(i);
  188.     }
  189. }
  190.  
  191. /*  stclos --- insert closure entry at pat [j] */
  192.  
  193. stclos (pat, j, lastj, lastcl)
  194. char pat (MAXPAT)
  195. int j, lastj, lastcl
  196. {
  197.  
  198.     int addset
  199.     int jp, jt, junk
  200.  
  201.     for (jp = j - 1; jp >= lastj; jp = jp - 1) {
  202.         /*  make a hole */
  203.         jt = jp + CLOSIZE
  204.         junk = addset (pat (jp), pat, jt, MAXPAT)
  205.     }
  206.     j = j + CLOSIZE
  207.     stclos = lastj
  208.     /* put closure in it */
  209.     junk = addset (CLOSURE, pat, lastj, MAXPAT) 
  210.     /* COUNT */
  211.     junk = addset (0, pat, lastj, MAXPAT)
  212.     /* PREVCL */
  213.     junk = addset (lastcl, pat, lastj, MAXPAT)
  214.     /* START */
  215.     junk = addset (0, pat, lastj, MAXPAT)
  216.     return
  217. }
  218.  
  219. /*  getccl --- expand char class at arg [i] into pat [j] */
  220.  
  221. getccl (arg, i, pat, j)
  222. char arg (MAXARG), pat (MAXPAT)
  223. int i, j
  224. {
  225.  
  226.     int jstart, junk
  227.     int addset
  228.  
  229.     i = i + 1      /*  skip over [ */
  230.     if (arg [i] == NOT) {
  231.         junk = addset (NCCL, pat, j, MAXPAT)
  232.         i = i + 1
  233.         }
  234.     else
  235.         junk = addset (CCL, pat, j, MAXPAT)
  236.     jstart = j
  237.     /* leave room for count */
  238.     junk = addset (0, pat, j, MAXPAT)
  239.     filset (CCLEND, arg, i, pat, j, MAXPAT)
  240.     pat (jstart) = j - jstart - 1
  241.     if (arg [i] == CCLEND)
  242.         getccl = OK
  243.     else
  244.         getccl = ERR
  245.  
  246.     return
  247. }
  248.  
  249. /*  patsiz --- returns size of pattern entry at pat [n] */
  250.  
  251.     int function patsiz (pat, n)
  252.     char pat (MAXPAT)
  253.     int n
  254.  
  255.     if (pat [n] == CHAR | pat [n] == START_TAG | pat [n] == STOP_TAG)
  256.         patsiz = 2
  257.     else if (pat [n] == BOL | pat [n] == EOL | pat [n] == ANY)
  258.         patsiz = 1
  259.     else if (pat [n] == CCL | pat [n] == NCCL)
  260.         patsiz = pat (n + 1) + 2
  261.     else if (pat [n] == CLOSURE)      /*  optional */
  262.         patsiz = CLOSIZE
  263.     else
  264.         error ("in patsiz: can't happen.")
  265.  
  266.     return
  267. }
  268.  
  269. /*  filset --- expand set at  array [i]  into  set [j],
  270.  *             stop at  delim.
  271.  */
  272.  
  273. filset (delim, array, i, set, j, maxset)
  274. char delim;
  275. char *array;
  276. int i;
  277. char *set;
  278. int *j;
  279. int maxset;
  280. {
  281.     string digits "0123456789"
  282.     string lowalf "abcdefghijklmnopqrstuvwxyz"
  283.     string upalf "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  284.  
  285.     for ( ; array [i] != delim && array [i] != EOS; i++) {
  286.         if (array [i] == ESCAPE) {
  287.             addset (esc(array,i), set, *j, maxset);
  288.         }
  289.         else if (array [i] != DASH) {
  290.             addset (array [i], set, j, maxset);
  291.         }
  292.         else if (j <= 1 | array (i + 1) == EOS) {
  293.             /*  literal - */
  294.             addset (DASH, set, j, maxset);
  295.         }
  296.         else if (index (digits, set (j - 1)) > 0) {
  297.             dodash (digits,array,i,set,j,maxset);
  298.         }
  299.         else if (index (lowalf, set (j - 1)) > 0)
  300.             dodash (lowalf,array,i,set,j,maxset);
  301.         }
  302.         else if (index (upalf, set (j - 1)) > 0) {
  303.             dodash (upalf,array,i,set,j,maxset);
  304.         }
  305.         else {
  306.             addset (DASH, set, j, maxset);
  307.         }
  308.     }
  309. }
  310.  
  311. /*  locate --- look for c in char class at pat (offset) */
  312.  
  313. int locate (c, pat, offset)
  314. char c;
  315. char *pat;
  316. int offset;
  317. {
  318.     int i
  319.  
  320.     /*  size of class is at pat (offset), chars follow */
  321.     for (i = offset + pat [offset]; i > offset; i--) {
  322.         if (c == pat [i]) {
  323.             return (YES);
  324.         }
  325.     }
  326.     return (NO)
  327. }
  328.  
  329. /*  dodash - expand array (i-1)-array (i+1
  330.  *           into set [j]... from valid
  331.  */
  332.  
  333.     subroutine dodash (valid, array, i, set, j, maxset)
  334.     int i, j, maxset
  335.     char valid (ARB), array (ARB), set (maxset)
  336.  
  337.     char esc
  338.  
  339.     int junk, k, limit
  340.     int addset, index
  341.  
  342.     i = i + 1
  343.     j = j - 1
  344.     limit = index (valid, esc (array, i))
  345.     for (k = index (valid, set [j]); k <= limit; k = k + 1)
  346.         junk = addset (valid [k], set, j, maxset)
  347.  
  348.     return
  349. }
  350. ---------- end comment out */
  351.  
  352.  
  353.  
  354. /*  addset - put c in string [j] if it fits, increment j
  355.  *
  356.  *           calling sequence:  addset (c, str, &j, maxsiz);
  357.  */
  358.  
  359. BOOL addset (c, str, j, maxsiz)
  360. char c;
  361. char *str;
  362. int *j;
  363. int maxsiz;
  364. {
  365.     if (*j >= maxsiz) {
  366.         return(NO);
  367.     }
  368.     else {
  369.         str[(*j)++] = c;
  370.         return(YES);
  371.     }
  372. }
  373.  
  374.  
  375. /* comment out ----------
  376.  
  377. /*  esc - map array [i] into escaped char if appropriate */
  378.  
  379. char esc (array, i)
  380. char *array;
  381. int i;
  382.  
  383.     if (array [i] != ESCAPE) {
  384.         return(array [i]);
  385.     }
  386.     else if (array (i+1) == EOS) {
  387.         /*  @ not special at end */
  388.         return(ESCAPE);
  389.     }
  390.     else {
  391.         i++;
  392.         if ( array [i] == 'n' || array [i] == 'N') {
  393.             return(NEWLINE);
  394.         }
  395.         else if (array [i] == 't' || array [i] == 'T'){
  396.             return(TAB);
  397.         }
  398.         else {
  399.             return(array [i]);
  400.         }
  401.     }
  402. }
  403.  
  404. /*  match --- find match anywhere on line */
  405.  
  406. match (lin, pat)
  407. char *lin, *pat;
  408. {
  409.  
  410.     int i, junk[9]
  411.  
  412.     for (i = 0; lin[i] != EOS; i++) {
  413.         if (amatch (lin, i, pat, junk, junk) > 0) {
  414.             return(YES);
  415.         }
  416.     }
  417.     return(NO);
  418. }
  419.  
  420. /*  amatch --- (non-recursive) look for match 
  421.  *             starting at lin (from)
  422.  */
  423.  
  424. amatch (lin, from, pat, tagbeg, tagend)
  425. char lin (MAXLINE), pat (MAXPAT)
  426. int from, tagbeg (10), tagend (10)
  427. {
  428.  
  429.     int i, j, offset, stack;
  430.  
  431.     for (i = 1; i <= 10; i = i + 1) {
  432.         tagbeg [i] = 0;
  433.         tagend [i] = 0;
  434.     }
  435.     tagbeg [1] = from;
  436.     stack = 0;
  437.     offset = from;      /*  next unexamined input char */
  438.  
  439.     for (j = 1; pat [j] != EOS; j = j + patsiz (pat, j)) {
  440.  
  441.         if (pat [j] == CLOSURE) {
  442.             /*  a closure entry */
  443.             stack = j
  444.             /* step over closure */
  445.             j += CLOSIZE 
  446.             for (i = offset; lin [i] != EOS; ) {
  447.                 /* match as many as possible */
  448.                 if (omatch(lin,i,pat,j) == NO){
  449.                     break;
  450.                 }
  451.             }
  452.             pat (stack + COUNT) = i - offset;
  453.             pat (stack + START) = offset;
  454.             /* char that made us fail */
  455.             offset = i;
  456.         }
  457.         else if (pat [j] == START_TAG) {
  458.             i = pat (j + 1);
  459.             tagbeg (i + 1) = offset;
  460.         }
  461.         else if (pat [j] == STOP_TAG) {
  462.             i = pat (j + 1)
  463.             tagend (i + 1) = offset
  464.         }
  465.         else if (omatch (lin, offset, pat, j) == NO) {  /*  non-closure */
  466.             for ( ; stack > 0; stack = pat (stack + PREVCL))
  467.                 if (pat (stack + COUNT) > 0)
  468.                     break
  469.             if (stack <= 0) {      /*  stack is empty */
  470.                 amatch = 0      /*  return failure */
  471.                 return
  472.             }
  473.             pat (stack + COUNT) = pat (stack + COUNT) - 1
  474.             j = stack + CLOSIZE
  475.             offset = pat (stack + START)  +  pat (stack + COUNT)
  476.         }
  477.     }
  478.     /*  else omatch succeeded */
  479.  
  480.     amatch = offset;
  481.     tagend [1] = offset;
  482.     return;      /*  success */
  483. }
  484.  
  485. /*  omatch --- try to match a single pattern at pat [j]
  486.  *             increment i.
  487.  */
  488.  
  489. BOOL omatch (lin, i, pat, j)
  490. char *line;
  491. int *i;
  492. char *pat;
  493. int j;
  494. {
  495.     int bump;
  496.  
  497.     if (lin [i] == EOS) {
  498.         return(NO);
  499.     }
  500.     bump = -1;
  501.     if (pat [j] == CHAR) {
  502.         if (lin [i] == pat [j + 1]) {
  503.             bump = 1;
  504.         }
  505.     }
  506.     else if (pat [j] == BOL) {
  507.         if (i == 1) {
  508.             bump = 0;
  509.         }
  510.     }
  511.     else if (pat [j] == ANY) {
  512.         if (lin [i] != NEWLINE) {
  513.             bump = 1;
  514.         }
  515.     }
  516.     else if (pat [j] == EOL) {
  517.         if (lin [i] == NEWLINE) {
  518.             bump = 0;
  519.         }
  520.     }
  521.     else if (pat [j] == CCL) {
  522.         if (locate (lin [i], pat, j + 1) == YES) {
  523.             bump = 1;
  524.         }
  525.     }
  526.     else if (pat [j] == NCCL) {
  527.         if ( lin [i] != NEWLINE &&
  528.              locate (lin [i], pat, j + 1) == NO
  529.            ) {
  530.             bump = 1;
  531.         }
  532.     }
  533.     else {
  534.         error ("in omatch: can't happen.");
  535.     }
  536.     if (bump >= 0) {
  537.         *i += bump;
  538.         return(YES);
  539.     }
  540.     else {
  541.         return(NO);
  542.     }
  543. }
  544. ---------- end comment out */
  545. (lin [i] == NEWLINE) {
  546.             bump = 0;
  547.         }
  548.     }
  549.     else if (pat [j] == CCL) {
  550.         if (locate (lin [i], pat, j + 1) == YES) {
  551.             bu